package binarytree

type TreeNode struct {
	val   int
	left  *TreeNode
	right *TreeNode
}

// 二叉树最近公共祖先-递归方法
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	if root.val == p.val || root.val == q.val {
		return root
	}
	left := lowestCommonAncestor(root.left, p, q)
	right := lowestCommonAncestor(root.right, p, q)
	if left != nil && right != nil {
		return root
	}
	if left == nil {
		return right
	}
	return left
}

// 二叉树最近公共祖先-存储父节点方法
func lowestCommonAncestor2(root, p, q *TreeNode) *TreeNode {
	parent := map[int]*TreeNode{} // key 是当前节点，value是父节点
	visited := map[int]bool{}     // visited是其中一个节点的向上地图
	var dfs func(*TreeNode)       // 深度优先探索
	dfs = func(r *TreeNode) {
		if r == nil {
			return
		}
		if r.left != nil {
			parent[r.left.val] = r
			dfs(r.left)
		}
		if r.right != nil {
			parent[r.right.val] = r
			dfs(r.right)
		}
	}
	dfs(root)
	for p != nil {
		visited[p.val] = true // 标记访问过
		p = parent[p.val]     // 依次取出p节点往上遍历
	}
	for q != nil {
		if visited[q.val] {
			return q
		}
		q = parent[q.val] //  依次取出q节点往上遍历
	}
	return nil
}

// 二叉搜索树的公共祖先，一个节点也可以是它自己的祖先，时间复杂度on 空间复杂度o1
// 一次遍历

func LowestCommonAncestorSearch(root, p, q *TreeNode) (ancestor *TreeNode) {
	ancestor = root // 从根节点开始遍历
	for {
		if p.val < ancestor.val && q.val < ancestor.val { // 当前节点值大于p q，说明p q应该在当前节点的左子树
			ancestor = ancestor.left
		} else if p.val > ancestor.val && q.val > ancestor.val { // 当前节点的值小于p q，说明p q应该在当前节点的右子树
			ancestor = ancestor.right
		} else { // 一大一小，或等于大小于
			// 分岔点 此时p q 要么在当前节点的不同子树中，要么其中一个就是当前节点
			return
		}
	}
}

// 二叉搜索树的第K大节点
//   3
// 1    4
//   2
// k=1 第1大节点
// 中序遍历，提前返回

func KthLargest(root *TreeNode) *TreeNode {
	dfs := func(root *TreeNode) {
		if root == nil {
			return
		}
	}
	dfs(root)
	return nil
}

// 判断平衡二叉树 二叉树的每个节点的左右子树的高度差的绝对值不超过 11
// 自底向上递归
// 时间复杂度on n是二叉树的节点个数，使用自底向上递归，每个节点的计算高度和判断是否为平衡二叉树只需要处理一次，最坏情况遍历所有节点
// 空间复杂度on n是二叉树的节点个数，主要取决于递归调用的层数，递归调用的层数不会超过n

func IsBalanced(root *TreeNode) bool {
	return height(root) >= 0
}

// 计算一颗二叉树的高
func height(root *TreeNode) int {
	if root == nil {
		return 0
	}
	max := func(x, y int) int {
		if x > y {
			return x
		}
		return y
	}
	abs := func(x int) int {
		if x < 0 {
			return -1 * x
		}
		return x
	}

	leftHeight := height(root.left)   // 求左树高
	rightHeight := height(root.right) // 求右树高
	if leftHeight == -1 || rightHeight == -1 || abs(leftHeight-rightHeight) > 1 {
		return -1
	}

	return max(leftHeight, rightHeight) + 1
}

// 先序遍历
func preOrderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	// 没有子树节点
	if root.left == nil && root.right == nil {
		return []int{root.val}
	}
	var res []int

	// 迭代方式
	//var stack []*TreeNode
	//stack = append(stack, root)
	//for len(stack) != 0 {
	//	e := stack[len(stack)-1]
	//	stack = stack[:len(stack)-1]
	//	res = append(res, e.val)
	//	if e.right != nil {
	//		stack = append(stack, e.right)
	//	}
	//	if e.left != nil {
	//		stack = append(stack, e.left)
	//	}
	//}

	// 递归调用
	res = append(res, root.val)
	if root.left != nil {
		res = append(res, preOrderTraversal(root.left)...)
	}
	if root.right != nil {
		res = append(res, preOrderTraversal(root.right)...)
	}
	return res
}

// 中序遍历
func inOrderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	if root.left == nil && root.right == nil {
		return []int{root.val}
	}

	var res []int
	// 递归调用方式
	// 先遍历左子树节点
	if root.left != nil {
		res = inOrderTraversal(root.left)
	}
	// 然后遍历父节点
	res = append(res, root.val)
	if root.right != nil {
		// 最后遍历右子树节点
		res = append(res, inOrderTraversal(root.right)...)
	}
	// 迭代方式略
	return res
}

// 后续遍历
func postOrderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var res []int
	// 递归调用方式
	// 先遍历左子树节点
	if root.left != nil {
		lRes := postOrderTraversal(root.left)
		if len(lRes) > 0 {
			res = append(res, lRes...)
		}
	}
	// 然后遍历右子树节点
	if root.right != nil {
		rRes := postOrderTraversal(root.right)
		if len(rRes) > 0 {
			res = append(res, rRes...)
		}
	}
	// 最后遍历父节点
	res = append(res, root.val)

	// 迭代方式略
	return res
}
